package leetcode.problems;

import org.junit.Test;

/**
 * Created by gmwang on 2018/7/25
 */
public class _0728MergeTwoBinaryTrees {
    /**
     * Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.
     *
     * You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.
     *
     * Example 1:
     * Input:
     * 	Tree 1                     Tree 2
     *           1                         2
     *          / \                       / \
     *         3   2                     1   3
     *        /                           \   \
     *       5                             4   7
     * Output:
     * Merged tree:
     * 	     3
     * 	    / \
     * 	   4   5
     * 	  / \   \
     * 	 5   4   7
     */
    /**
     *
     * @param t1,t2
     * @return
     */
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        // 任一不为空
        if (t1 == null && t2 == null) return null;

        if(t1 == null) return t2;
        if(t2 == null) return t1;

        TreeNode node = new TreeNode(t1.val + t2.val);
        node.left = mergeTrees(t1.left,t2.left);
        node.right = mergeTrees(t1.right,t2.right);
        return node;
    }

    @Test
    public void test() {
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode1L = new TreeNode(3);
        TreeNode treeNode1R = new TreeNode(2);
        TreeNode treeNode1LL = new TreeNode(5);
        treeNode1.left = treeNode1L;
        treeNode1.right = treeNode1R;
        treeNode1L.left = treeNode1LL;
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode2L = new TreeNode(1);
        TreeNode treeNode2R = new TreeNode(3);
        treeNode2.left = treeNode2L;
        treeNode2.right = treeNode2R;
        TreeNode treeNode2LR = new TreeNode(4);
        TreeNode treeNode2RR = new TreeNode(7);
        treeNode2L.right = treeNode2LR;
        treeNode2R.right = treeNode2RR;
        TreeNode res = mergeTrees(treeNode1,treeNode2);
        System.out.println(res);
    }

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode(int x) { val = x; }
     * }
     */
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) {
            val = x;
        }
    }
}
